#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 136. 只出现一次的数字.py
@time: 2022/1/29 16:45
@desc: https://leetcode-cn.com/problems/single-number/
> 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
示例 1:
    输入: [2,2,1]
    输出: 1

@解题思路：
    1. 排序、遍历, Ot(N), Os(1)
    2. 异或： 正经人想不出来： Ot(n), Os(1)
            1. 任何数和 0 做异或运算，结果仍然是原来的数，即a⊕0=a。
            2. 任何数和其自身做异或运算，结果是 0，即 a⊕a=0。
            异或运算满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。

            作者：LeetCode-Solution
            链接：https://leetcode-cn.com/problems/single-number/solution/zhi-chu-xian-yi-ci-de-shu-zi-by-leetcode-solution/
            来源：力扣（LeetCode）
            著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
'''


class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) < 2: return nums[0]
        nums.sort()
        n = len(nums)
        # 边界情况
        if not nums[0] == nums[1]: return nums[0]
        for i in range(1, n - 1):
            if not nums[i - 1] == nums[i] and not nums[i] == nums[i + 1]:
                return nums[i]
        # 边界情况
        if not nums[-1] == nums[-2]: return nums[-1]
        return -1

class Solution2(object):
    """
    异或运算
    """
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        single = 0
        for num in nums:
            single ^= num
        return single
